import java.util.LinkedList;

/*****************************************************
 *
 * ALGORITMOS Y ESTRUCTURA DE DATOS
 * HOJA DE TRABAJO 7 
 * YUCELY BEB 12537
 * VICTOR FUENTES 12298
 * 
 * CLASE PARA REPRESENTAR EL ARBOL BINARIO DE HUFFMAN
 ******************************************************/
public class HuffmanTree {
    
    //uso de java collection frame para la lista de base 
    //para la construccion del arbol binario de huffman
    public LinkedList<Arbol<Cadena>> lista;
    
    //variable para la cadena de letras
    public String cadenabase;
    
    //frecuencia de los caracteres
    public int[] frec;
    
    public HuffmanTree(){
        lista=new LinkedList();
        cadenabase="ABBASSDAERSAAASCSAS ";
        frec=new int[cadenabase.length()];
    }
    
    //inicializar la frecuencia
    public void initFrecuencia(){
        for(int j=0;j < frec.length;j++){
            frec[j]=0;
        }
    }
    
    //metodo para crear un arbol binario
    public void initArbol(){
        for(int q=0; q < frec.length;q++){
            if(frec[q]>0){
                Cadena temp=new Cadena();
                temp.setFrecuencia(frec[q]);
                temp.setCadena(cadenabase.substring(q, q+1));
                Arbol<Cadena> arboll = new Arbol();
                arboll.setValor(temp);
                agregarArbol(arboll);
                
            }
        }
    }
    
    
    //creacoin de arbol binario de huffman
    public void initHuffmanTree(){
        String str;
        int freq;
        while(lista.size()> 1){
            str=lista.get(0).getValor().getCadena()+lista.get(1).getValor().getCadena();
            freq=lista.get(0).getValor().getFrecuencia()+lista.get(1).getValor().getFrecuencia();
            Arbol<Cadena> temp = new Arbol();
            temp.setValor(new Cadena(str,freq));
            temp.setIzquierda(lista.removeFirst());
            temp.setDerecha(lista.removeFirst());
            lista.addFirst(temp);
        }
    }
    
    //metodo para agregar hijos al arbol segun caracter
    public void agregarArbol(Arbol<Cadena> carac){
        boolean find=false;
        int contador=0;
        if(lista.size()==0){
            lista.add(0,carac);
        }else{
            while(!find){
                if(contador==lista.size()){
                    lista.add(contador,carac);
                    find=true;
                }else{
                    if(carac.getValor().getFrecuencia()> lista.get(contador).getValor().getFrecuencia() ){
                        contador++;
                    }else{
                        lista.add(contador,carac);
                        find=true;
                    }
                }
                    
            }
        }
    }
    
    
    //metodo para inicializar los codigos de los caracteres
    //en el arbol de huffman
    
    public void initCodigo(){
        String right="0";
        String left="1";
        String code;
        Cadena cade=lista.getFirst().getValor();
        for(int i=0;i<cade.getCadena().length();i++){
            Arbol<Cadena> temp = lista.getFirst();
            code="";
            
            while(!((temp.getIzquierda() == null) && (temp.getDerecha() == null))){
                if(temp.getIzquierda().getValor().getCadena().contains(cade.getCadena().substring(i, i+1))){
                    temp=temp.getIzquierda();
                    code=code+left;
                }else{
                    temp=temp.getDerecha();
                    code=code+right;
                }
                
                
                
            }
            
            temp.getValor().setCodigo(code);
            
        }
    }
    
    
    //metodo para procesar el mensaje desde teclado
    public void procesar(String str){
        str=str.toUpperCase();
        initFrecuencia();
        for(int i=0; i<str.length();i++){
            frec[cadenabase.indexOf(str.charAt(i))]++;
            
        }
        initArbol();
        initHuffmanTree();
        initCodigo();
        
    }
    
    
    //metodo para imprimri en columans la informacion 
    public String toString(){
        String resultado="Letra              Frecuencia         Codigo Binario";
        Cadena cade=lista.getFirst().getValor();
        String[] array=new String[cade.getCadena().length()+1];
        array[0]=resultado;
        for(int i=0;i < cade.getCadena().length(); i++ ){
            Arbol<Cadena> temp = lista.getFirst();
            while(!((temp.getIzquierda() == null) && (temp.getDerecha() == null)))
            {
                if (temp.getIzquierda().getValor().getCadena().contains(cade.getCadena().substring(i, i+1)))
                    temp=temp.getIzquierda();
                else
                    temp=temp.getDerecha();
            }
            array[i+1]=("   " + temp.getValor().getCadena() + "                           " + temp.getValor().getFrecuencia() + "                            " + temp.getValor().getCodigo());
        }
        //for para recorrer todo el arreglo 
        for (int i = 1; i < array.length - 1; i++)
            for(int j = i; j < array.length; j++)
            {
                if(array[i].charAt(0) > array[j].charAt(0))
                {
                    resultado = array[i];
                    array[i] = array[j];
                    array[j] = resultado;
                }
            }
        resultado = "";
        for (int i = 0; i < array.length; i++){
           resultado =resultado+array[i]+"\n"; 
        }     
        return resultado;
    }
    
    
}
